#include "CmpMngr.h"

using namespace std;

/*********************
compare
Calls the needed routines to get the final count of the differences between two files.
********************/
void CmpMngr::compare(srcLineVector* baseFileMap, srcLineVector* compFileMap, double match_threshold)
{
  MATCH_THRESHOLD = match_threshold;
  nNochangedLines = nChangedLines = nAddedLines = nDeletedLines = 0;
  
  find_unmodified_lines(baseFileMap,compFileMap);
  
  find_modified_lines(baseFileMap,compFileMap);
  //Remaining lines are added or deleted, no further details needed to be searched.
  for (srcLineVector::iterator i = baseFileMap->begin(); i != baseFileMap->end(); i++)
  {
	  nDeletedLines += (*i).second;
  }
  for (srcLineVector::iterator i = compFileMap->begin(); i != compFileMap->end(); i++)
  {
	  nAddedLines += (*i).second;
  }
}

/*
find_modified_lines()
Finds number of modified lines, anything remaining in lists is either delted or added.
swapped lines and number of (disabled)
*/
void CmpMngr::find_modified_lines (srcLineVector* aHm,srcLineVector* bHm)
{
	srcLineVector* listA;
	srcLineVector* listB;
	if (aHm->size() == 0 || bHm->size() == 0)
	{
		return;
	}
	//This picks the shortest list to do the sorting on.
	if (aHm->size() > bHm->size())
	{
		listA = bHm;
		listB = aHm;
	}
	else
	{
		listA = aHm;
		listB = bHm;
	}
	/*
		This creates a map of string size -> [iterators]
		This is used to quickly access the locations of lines that are in valid size range of modified line for the given search line.
	*/
	stringSizeMap mySSList;
	for (srcLineVector::iterator myI = listA->begin(); myI != listA->end(); myI++)
	{
		pair <stringSizeMap::iterator,bool> myResult;
		stringList myList((*myI).second, (*myI).first);//populate with the number of copies of this string
		myResult = mySSList.insert(make_pair((int)(*myI).first.size(),myList));
		if (!myResult.second)
		{	//already had a copy of something this size
			(*myResult.first).second.insert((*myResult.first).second.begin(),myList.begin(),myList.end());//append the list
		}
	}
	/*
		This iterates through the longer list and searches for modified lines in the shorter list.
		It finds the min and max size range for modified lines and only looks through those specific locations.
		Since the map is sorted, lookup using find is log(n) to get the iterator .
		
		Once an entry is found of a list of lines that have the same size in valid modified range, checks each to see if 
		it is modified. 
	*/
	for (srcLineVector::iterator myI = listB->begin(); myI != listB->end(); )
	{
		//find the valid size range (dictated by the MATCH_TRESHOLD)
		int minSize = (int)((*myI).first.length() * (MATCH_THRESHOLD / 100));
		int maxSize = (int)((*myI).first.length() / (MATCH_THRESHOLD / 100));
		bool deleted = false;
		bool deletedA = false;
		for (int i = minSize; i <= maxSize; i++)
		{
			stringSizeMap::iterator mySSI = mySSList.find(i);//find the list of strings of this length
			if (mySSI != mySSList.end())
			{	//found some
				for (stringList::iterator mySLI = (*mySSI).second.begin(); mySLI != (*mySSI).second.end(); )
				{
					if (similar_line((*mySLI),(*myI).first))
					{
						string prev = (*mySLI);						
						srcLineVector::iterator listAi = listA->find((*mySLI));
						//This while loop eliminates the need to call similar_line function on every entry if they are the same
						while ((*myI).second > 0 
							&& (mySLI != (*mySSI).second.end() 
							&& (*mySLI) == prev))
						{
							(*myI).second--;
							(*listAi).second--;
							stringList::iterator tmpSLI = mySLI++;
							(*mySSI).second.erase(tmpSLI);
							deletedA = true;
							nChangedLines++;
						}
						if ((*myI).second == 0)
						{
							srcLineVector::iterator tmpI = myI++;
							listB->erase(tmpI);
							deleted = true;
						}
						if ((*listAi).second == 0)
						{
							listA->erase(listAi);
						}
						if (deleted || deletedA)
						{
							break;
						}						
					}
					else
					{
						mySLI++;
					}
				}
				if (deleted || deletedA)
				{
					break;
				}
			}
		}
		if (!deleted)
		{
			myI++;
		}
	}
}

/*
	find_unmodified_lines
	Does a binary search to find unmodified lines, relies on fact that they are in 
	STL hash (srcLineVector) so they are already sorted and the find function is log(n)
*/
void CmpMngr::find_unmodified_lines(srcLineVector* aHm,srcLineVector* bHm)
{
	srcLineVector* listA;
	srcLineVector* listB;
	if (aHm->size() > bHm->size())
	{
		listA = bHm;
		listB = aHm;
	}
	else
	{
		listA = aHm;
		listB = bHm;
	}	
	for (srcLineVector::iterator myI = listA->begin(); myI != listA->end(); )
	{
		bool deleted = false;
		srcLineVector::iterator result;
		result = listB->find((*myI).first);
		if (result != listB->end())
		{
			while ((*myI).second > 0 && (*result).second > 0)
			{
				(*myI).second--;
				(*result).second--;
				nNochangedLines++;
			}
			if ((*myI).second == 0)
			{
				srcLineVector::iterator tmpI = myI++;
				listA->erase(tmpI);
				deleted = true;
			}
			if ((*result).second == 0)
			{
				listB->erase(result);
			}
		}
		if (!deleted)
		{
			myI++;
		}
	}
}

/************************
similar_line, J. Kim 10/09/2006
- revised version of the original method
- order of characters taken into account
- criteria for determining 'similar lines' :
     length(LCS) / length(baseLine) * 100 >= MATCH_THRESHOLD
                             &&
	 length(LCS) / length(compLine) * 100 >= MATCH_THRESHOLD
- above criteria solves two problems encountered in the original function
	<1>	
		similar_lines("ABC", "ABCDEF") = 1
		similar_lines("ABCDEF", "ABC") = 0
		=> because of this, if we modify a line from the original file, sometimes
		we get 1 MODIFIED and sometimes get 1 ADDED + 1 DELETED.
	<2>
		"ABCDEF" and "FDBACE" classified as similar lines(order not taken 
		into account)
		=> because of this, when we delete a certain line from the original 
			file and insert a new one, instead of getting 1 ADDED and 1 DELETED,
			we might get 1 MODIFIED.
			(ex)
			DELETE: out = "test sentence";
			INSERT: cout << "censstetetne";
			and get 1 MODIFIED 
			instead of getting 1 ADDED + 1 DELETED
************************/
bool CmpMngr::similar_line(string baseLine, string compareLine)
{
  int m,n,i,j,k;
  m = n = i = j = k = 0;
  double LCSlen = 0;
  m=(int)baseLine.size(); n=(int)compareLine.size();
  vector<int> x1,x2;
  x1.resize(m+1,0); x2.resize(m+1,0);

  //compute length of LCS
  // - no need to use CBitMatrix

  for (j=n-1; j>=0; j--)
  {
	  for (k=0; k<=m;k++)
	  {
		  x2[k] = x1[k];
		  x1[k] = 0;
	  }
	  for (i=m-1; i>=0; i--)
	  {
		  if (baseLine[i] == compareLine[j])
		  {
			  x1[i] = 1 + x2[i+1];
		  }
		  else
		  {
			  if (x1[i+1] > x2[i])
			  {
				  x1[i] = x1[i+1];
			  }
			  else
			  {
				  x1[i] = x2[i];
			  }
		  }
	  }
  }
  LCSlen = x1[0];
  if ((LCSlen / (double)m * 100 >= MATCH_THRESHOLD) &&
	  (LCSlen / (double)n * 100 >= MATCH_THRESHOLD))
	  return true;
  else 
	  return false;
}
